/* Copyright (C) 2007 Notyet

这是algebra库的一部分。

algebra是一个基于C开发的库，旨在解决代数式化简与解简单方程的问题。

联系方式：
E-Mail:nt1900@gmail.com  */

#include "alglib.h"

unsigned int gcd(unsigned int x,unsigned int y)
{
// common divisor最大公约数
// 据说是最快的算法
// 引自 http://www.cppblog.com/asp/archive/2006/10/22/14012.html
	unsigned int i,j,t;
	if(x==0)return y;
	if(y==0)return x;
	for(i=0;0==(x&1);x>>=1,++i);
	for(j=0;0==(y&1);y>>=1,++j);
	if(j<i)i=j;
	for(;;)
	{
		if(x<y)t=y,y=x,x=t;
		if(0==(x-=y))return y<<i;
		for(;0==(x&1);x>>=1);
	}
}


